package fun.coding.leetcode;

import java.util.Stack;

public class MinStack {

	public static void main(String[] args) {
		// push(1),push(2),top,getMin,pop,getMin,top
	}
	
	private Stack<Integer> stack = new Stack<Integer>();
	// Keep the minimum value so far
	// For this problem, if you don't want to use 2 stacks, use define a node that contains the current minimum as a field.
	// http://blog.csdn.net/ljiabin/article/details/40982153
	// A follow up question
	// how do you design a queue that can push, pop, top, and getMinimum in O(1) time
	// Answer is using 2 queues,whenever a smaller element is added to the queue, just clear the queue
	// push 1, 3, 0, 4
	// minQueue = 1, 3, 0 comes, then minQueue = 0, then [0, 4], head is always the smallest
	// and a sliding window problem will be solved. 
	// http://leetcode.com/2011/01/sliding-window-maximum.html
	private Stack<Integer> minStack = new Stack<Integer>();
	
    public void push(int x) {
        stack.add(x);
        
        if (minStack.isEmpty()) {
        	minStack.add(x);
        } else {
        	if (x <= minStack.peek()) {
        		minStack.add(x);
        	}
        }
    }

    public void pop() {
        if (stack.isEmpty()) return;
        
        int v = stack.pop();
        
        if (v == minStack.peek()) {
        	minStack.pop();
        }
    }

    public int top() {
    	if (stack.isEmpty()) return 0;
    	
    	return stack.peek();
    }

    public int getMin() {
        return minStack.peek();
    }
}
